'''
https://leetcode.cn/problems/can-i-win/description/
'''
from functools import cache


class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal == 0: return True
        # 假设每人都选平均值，是否reach total
        can_reach_desiredTotal = ((1 + maxChoosableInteger) // 2 * maxChoosableInteger) >= desiredTotal // 2
        if not can_reach_desiredTotal: return False


        status = (1 << maxChoosableInteger) - 1
        @cache
        def f(status, rest):
            if rest <= 0:
                return False
            for b in range(maxChoosableInteger):
                if (status >> b) & 1:
                    choose = b + 1
                    # 如果我能够，或者对手必输
                    if not f(status - (1 << b), rest - choose):
                        return True
            return False
        return f(status, desiredTotal)


maxChoosableInteger = 10
desiredTotal = 40
print(Solution().canIWin(maxChoosableInteger, desiredTotal))